Amazon MWSのAPIをコールしても InvalidParameterValue エラーが返ってきてしまう

Amazon MWSを使用してプログラムを作成しようとしています。
こちらの仕様書を見て実装していますが、何か抜けている状態です。

http://docs.developer.amazonservices.com/ja_JP/dev_guide/DG_ClientLibraries.html

# -*- coding:utf-8 -*-
from time import strftime, gmtime
from requests import request
import base64
import hashlib
import hmac
import urllib.parse

param = {
    'AWSAccessKeyId': 'xxxx',
    'Action': 'ListMatchingProducts',
    'SellerId': 'xxxx',
    'SignatureMethod': 'HmacSHA256',
    'SignatureVersion': '2',
    'Timestamp': strftime("%Y-%m-%dT%H:%M:%SZ", gmtime()),
    'Version': '2011-10-01',
    'Query': "harrypotter"
}

data = "POSTnmws.amazonservices.jpnProducts/2011-10-01n/"
format_param = "&".join(['{0}={1}'.format(key, urllib.parse.quote(param[key], safe='-_.~').encode('utf-8')) for key in sorted(param)])
before_sign_data = "{0}{1}".format(data, format_param)
hmacstr = hmac.new(b"secretKey", bytes(before_sign_data.encode('UTF-8')), hashlib.sha256).digest()
base64str = base64.b64encode(hmacstr)

url = "{0}{1}?{2}&Signature={3}".format("https://mws.amazonservices.jp", "/Products/2011-10-01", format_param, urllib.parse.quote(base64str))
headers = {'User-Agent': 'python-app-mws/0.0.1 (Language=Python)'}
response = request("POST", url_param, data={}, headers=headers)
data = response.content

print(data)

実行時のエラーは、以下になります。

b'<?xml version="1.0"?>n<ErrorResponse xmlns="https://mws.amazonservices.com/">n  <Error>n    <Type>Sender</Type>n    <Code>InvalidParameterValue</Code>n    <Message>Value b&apos;2&apos; for parameter SignatureVersion is invalid.</Message>n  </Error>n  <RequestID>6e29a554-c2d2-4b23-9f99-276aa250d239</RequestID>n</ErrorResponse>n'

送信時のURLは、以下のようになっていました。

https://mws.amazonservices.jp/Products/2011-10-01?AWSAccessKeyId=b'xxxxx'&Action=b'ListMatchingProducts'&Query=b'harry%20potter'&SellerId=b'xxxxx'&SignatureMethod=b'HmacSHA256'&SignatureVersion=b'2'&Timestamp=b'2017-03-07T15%3A22%3A32Z'&Version=b'2011-10-01'&Signature=v/lujNiPl8NZTkWmDQXRsAfhiX1GTLOOE7erK26QHDA%3D

何かお気づきのところあれば、教えて頂けれたら幸いです。

format_param = "&".join(['{0}={1}'.format(key, urllib.parse.quote(param[key], safe='-_.~')) for key in sorted(param)])